package sourcecodes;


import com.sun.org.apache.regexp.internal.RE;

/**
 * 1.创建RBTree，定义颜色
 * 2.创建RBNode
 * 3.辅助方法定义：parentOf(node),isRed(node),isBlack(node),setRed(node),setBlack(node),inOrderPrint()
 * 4.左旋方法定义
 * 5.右旋方法定义
 * 6.公开插入接口方法定义
 * 7.内部插入接口方法定义
 * 8.修正插入导致红黑树失衡的方法定义：
 * 9.测试红黑树正确性
 *
 * @param <K>
 */
public class RBTree<K extends Comparable<K>, V> {
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private RBNode root;

    public RBNode getRoot() {
        return root;
    }

    private RBNode parentOf(RBNode node) {
        if (node != null) {
            return node.parent;
        }
        return null;
    }

    private boolean isRed(RBNode node) {
        if (node != null) {
            return node.color == RED;
        }
        return false;
    }

    private void setRed(RBNode node){
        if (node != null) {
            node.color = RED;
        }
    }

    private void setBlack(RBNode node){
        if (node != null) {
            node.color = BLACK;
        }
    }

    private boolean isBlack(RBNode node) {
        if (node != null) {
            return node.color == BLACK;
        }
        return false;
    }


    public void inOrderPrint() {
        inOrderPrint(root);
    }

    private void inOrderPrint(RBNode node) {
        if (node != null) {
            inOrderPrint(node.left);
            System.out.println("key -> " + node.key + " | " + "value -> " + node.value);
            inOrderPrint(node.right);
        }
    }


    public void insert(K key,V value){
        RBNode node = new RBNode();
        node.setKey(key);
        node.setValue(value);
        // 新节点一定是红色
        node.setColor(RED);
        insert(node);
    }

    private void insert(RBNode node) {
        // 1.find  root
        RBNode parent = null;
        RBNode x = this.root;

        while (x != null) {
            parent = x;

            // cmp > 0 , noed.key  > x.key 需要到x的右子树查找
            int cmp = node.key.compareTo(x.key);
            if (cmp > 0) {
                x = x.right;
            } else if (cmp == 0) {
                x.setValue(node.getValue());
                return;
            } else {
                x = x.left;
            }
        }

        node.parent = parent;
        // node与parent
        if(parent != null){
            int cmd = node.key.compareTo(parent.key);
            if(cmd > 0){// 当前node的key比parent大
                parent.right = node;
            } else {
                parent.left=  node;
            }
        }else {
            this.root = node;
        }

        //update balence
        insertFixUp(node);
    }

    /**
     *
     * 插入后修复红黑树平衡的方法：
     *
     *          1. 红黑树为空 跟节点给黑色
     *          2。插入节点的key已经存在  不需要处理
     *          3。插入节点的父节点为黑色   不影响黑平衡
     *
     *          4。需要自己去处理 （插入节点的父节点是红色）
     *              4。1叔叔 节点存在，并且为红色（父叔双红）将爸爸和叔叔染色为黑色，并且以爷爷节点为当前节点，进行下一轮处理
     *              4。2叔叔节点不存在，或者为黑色，父节点为爷爷节点的左子树。
     *                      4。2。1插入节点为其父节点的【左】子节点情况(LL)将爸爸染色成黑色，爷爷为红色，以爷爷右旋
     *                      4。2。2插入节点为其父节点的【右】子节点情况(LR)以爸爸进行左旋，得到LL（4。2。1）指定爸爸为当前 进行下一轮处理
     *              4。3叔叔节点不存在，或者为黑色，父节点为爷爷节点的右子树。
     *                      4。3。1插入节点为其父节点的【右】子节点情况(RR)将爸爸染色成黑色，爷爷为红色，以爷爷左旋
     *                      4。3。2插入节点为其父节点的【左】子节点情况(RL)以爸爸进行右旋，得到RR（4。3。1）指定爸爸为当前 进行下一轮处理
     *
     *
     */
    private void insertFixUp(RBNode node){
        root.setColor(BLACK);

        RBNode parent = parentOf(node);
        RBNode gparent = parentOf(parent);

        RBNode uncle = null;
        // 情景4 插入节点父节点为红
        if(parent != null && isRed(parent)){
            // 如果父节点是红色，那么一定存在爷爷节点，因为跟节点不可能是红色。
            if(parent == gparent.left){
                uncle = gparent.right;

                // 4.1
                if(uncle != null && isRed(uncle)){
                    // 将爸爸和叔叔染色为黑色，并且以爷爷节点为当前节点，进行下一轮处理
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(gparent);
                    insertFixUp(gparent);
                    return;
                }
                // 4。2叔叔节点不存在，或者为黑色，父节点为爷爷节点的左子树。
                if(uncle == null || isBlack(uncle)){
                    // 4。2。1插入节点为其父节点的【左】子节点情况(LL)将爸爸染色成黑色，爷爷为红色，以爷爷右旋
                    if(node == parent.left){
                        setBlack(parent);
                        setRed(gparent);
                        rightRotate(gparent);
                    }
                    //4。2。2插入节点为其父节点的【右】子节点情况(LR)以爸爸进行左旋，
                    // 得到LL（4。2。1）指定爸爸为当前 进行下一轮处理
                    if(node == parent.right){
                        leftRotate(parent);
                        insertFixUp(parent);
                        return;
                    }
                }
            }
        }else { // 父节点为爷爷节点的右子树
            uncle  = parent.left;
            // 4.1
            if(uncle != null && isRed(uncle)){
                // 将爸爸和叔叔染色为黑色，并且以爷爷节点为当前节点，进行下一轮处理
                setBlack(parent);
                setBlack(uncle);
                setRed(gparent);
                insertFixUp(gparent);
                return;
            }
            // 4。3叔叔节点不存在，或者为黑色，父节点为爷爷节点的右子树。
            if(uncle == null || isBlack(uncle)){
                //4。3。1插入节点为其父节点的【右】子节点情况(RR)
                // 将爸爸染色成黑色，爷爷为红色，以爷爷左旋
                if(node == parent.right){
                    setBlack(parent);
                    setRed(gparent);
                    leftRotate(gparent);
                    return;
                }
                // 4。3。2插入节点为其父节点的【左】子节点情况(RL)
                // 以爸爸进行右旋，得到RR（4。3。1）指定爸爸为当前 进行下一轮处理
                if(node == parent.left){
                    rightRotate(parent);
                    insertFixUp(parent);
                    return;
                }
            }
        }
    }


    /**
     * 左旋方法：
     *左旋示意图：左旋 X 节点
     *
     *          P                              P
     *          |                              |
     *          X                              y
     *         / \          ------>           / \
     *        lx  y                          X   ry
     *           / \                        / \
     *          ly  ry                     lx ly
     *  1.将x的右子节点指向y的左子节点(ly),并将y的左子节点的父节点更新为x，
     *  2.当x的 父节点（不为空时），更新y的父节点为x的父节点，并将x的父节点指定子树（当前x的子树位置）指定为y
     *  3.将x的父节点更新为y，将y的左子节点更新为x
     *
     */
    private void leftRotate(RBNode x) {
        RBNode y = x.right;
        // 1.将x的右子节点指向y的左子节点(ly),并将y的左子节点的父节点更新为x，
        x.right = y.left;
        if (y.left != null) {
            y.left.parent = x;
        }

        // 2.当x的 父节点（不为空时），更新y的父节点为x的父节点，并将x的父节点指定子树（当前x的子树位置）指定为y
        if (x.parent != null) {
            y.parent = x.parent;

            if (x == x.parent.left) {
                x.parent.left = y;
            } else {
                x.parent.right = y;
            }
        } else {
            // x为跟节点，此时需要更新y为跟节点引用
            this.root = y;
            this.root.parent = null;
        }

        // 3.将x的父节点更新为y，将y的左子节点更新为x
        x.parent = y;
        y.left = x;
    }

    /**
     *
     * 右旋方法：
     *      *右旋示意图：左旋 y 节点
     *      *
     *      *          P                              P
     *      *          |                              |
     *      *          X                              y
     *      *         / \          <-----            / \
     *      *        lx  y                          X   ry
     *      *           / \                        / \
     *      *          ly  ry                     lx ly
     *
     *  1.将y的左子节点指向x的右子节点，并且更新x的右子节点父节点为y
     *  2.当y的父节点不为空时，更新x父节点为y父节点，更新y的父节点指定子节点（y当前位置）为x
     *  3.更新y的父节点为x，更新x的右 子节点为y
     */
    private void rightRotate(RBNode y) {
        RBNode x = y.left;
        // 1.将y的左子节点指向x的右子节点，并且更新x的右子节点父节点为y
        y.left = x.right;
        if (x.right != null) {
            x.right.parent = y;
        }
        // 2.当y的父节点不为空时，更新x父节点为y父节点，更新y的父节点指定子节点（y当前位置）为x
        if (y.parent != null) {
            x.parent = y.parent;
            if (y == y.parent.left) {
                y.parent.left = x;
            } else {
                y.parent.right = x;
            }

        }else {
            this.root = x;
            this.root.parent = null;
        }
        // 3.更新y的父节点为x，更新x的右 子节点为y
        y.parent = x;
        x.right = y;

    }

    static class RBNode<K extends Comparable<K>, V> {
        private RBNode parent;
        private RBNode left;
        private RBNode right;
        private boolean color;
        private K key;
        private V value;

        public RBNode(){

        }

        public RBNode(RBNode parent, RBNode left, RBNode right, boolean color, K key, V value) {
            this.parent = parent;
            this.left = left;
            this.right = right;
            this.color = color;
            this.key = key;
            this.value = value;
        }

        public RBNode getParent() {
            return parent;
        }

        public void setParent(RBNode parent) {
            this.parent = parent;
        }

        public RBNode getLeft() {
            return left;
        }

        public void setLeft(RBNode left) {
            this.left = left;
        }

        public RBNode getRight() {
            return right;
        }

        public void setRight(RBNode right) {
            this.right = right;
        }

        public boolean isColor() {
            return color;
        }

        public void setColor(boolean color) {
            this.color = color;
        }

        public K getKey() {
            return key;
        }

        public void setKey(K key) {
            this.key = key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }
    }

}
